#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LEN 7

void swap(int * a, int * b)
{
    *b = *a ^ *b;
    *a = *a ^ *b;	// now *a = *b
    *b = *a ^ *b;	// now *b = *a
}

void bubblesort(int * a, int n)
{
    int i, j;

    for (i = 0; i < n - 1; i++)
	for (j = n - 1; j >= i+1; j --)
	    if (a[j] < a[j-1])
		swap(&a[j], &a[j-1]);
}

void print_array_n (int * a, int n)
{
    int i;

    printf("array[%d]: ", n);
    for (i = 0; i < n; i++)
	//printf("[%d]--%d\t", i, a[i]);
	printf("%d\t", a[i]);
    printf("\n\n");
}

static int inversions;
void merge(int * a, int p, int q, int r)
{
    int l1, l2;
    int * L, * R;
    int i, j, k;

    l1 = q - p + 1;
    l2 = r - q;
    L = (int*)malloc(sizeof(int) * (l1 + 1));
    R = (int*)malloc(sizeof(int) * (l2 + 1));

    for (i = p; i <=q; i ++)
	L[i - p] = a[i];
    L[i - p] = 0x7fffffff;
    for (i = q + 1; i <=r; i++)
	R[i-q-1] = a[i];
    R[i-q-1] = 0x7fffffff;

    for (k = p, i = 0, j = 0; k <= r; k ++)
	if (L[i] <= R[j])
	    a[k] = L[i ++];
	else {
	    inversions += l1 - i;
	    a[k] = R[j ++];
	}
}

void merge_sort(int * a, int l, int r)
{
    int m;

    if (l < r) {
	m = (l + r) / 2;
	merge_sort (a, l, m);
	merge_sort (a, m+1, r);
	merge (a, l, m, r);
    }
}

void insertion_sort (int * a, int p, int q)
{
    int i, j;
    int v;

    for (i = p + 1; i <= q; i ++) {
	v = a[i];
	for (j = i - 1; j >= p; j --)
	    if (a[j] > v)
		a[j + 1] = a[j];
	    else
		break;
	a[j + 1] = v;
    }

}

void insertion_sort_bs (int * a, int p, int q)
{
    int i, j;
    int v;
    int low, high, mid;

    for (i = p + 1; i <= q; i ++) {
	v = a[i];
	// find index to insert into
	low = p;
	high = i - 1;
	while (low <= high) {
	    mid = (low + high) / 2;
	    if (a[mid] > v)
		high = mid - 1;
	    else
		low = mid + 1;
	}
	// a[high + 1] is the place to put v
	// low = high + 1 ? Yes!
	// first to move a[high + 1]......a[q] back one step
	for (j = i - 1; j >= high + 1; j --)
	    a[j + 1] = a[j];
	a[high + 1] = v;
	// to justify the relationship between low and high
	printf("high %d, low %d\n", high, low);
    }
}

int trimdump(int *a, int n)
{
    int i, j;
    int iVal;

    for (i = 0, j = i + 1; j < n; j++) {
	iVal = a[j];
	if (a[i] != iVal)
	    a[++i] = iVal;	    
    }

    return i;
}

int main()
{
#if 1	// test all kinds of sorting algorithms
    int i;
    int a[LEN];

    srand(time(NULL));
    for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	a[i] = rand() % 20;

    print_array_n(a, sizeof(a) / sizeof(a[0]));
    //bubblesort(a, sizeof(a) / sizeof(a[0]));
    merge_sort(a, 0, sizeof(a) / sizeof(a[0]) - 1);
    print_array_n(a, sizeof(a) / sizeof(a[0]));
    printf("%d inversions\n",  inversions);
    //insertion_sort (a, 0, sizeof(a) / sizeof(a[0]) - 1);
    // insertion_sort_bs (a, 0, sizeof(a) / sizeof(a[0]) - 1);
    // print_array_n(a, sizeof(a) / sizeof(a[0]));
#endif

#if 0	// test trimdump
    int a[LEN];
    int iNewEnd;
    int i;

    srand(time(NULL));
    a[0] = rand() % 10;
    for (i = 1; i < LEN; i++)
	a[i] = a[i-1] + rand() % 2;
    print_array_n(a, LEN); 
    iNewEnd = trimdump(a, LEN);
    print_array_n(a, iNewEnd + 1);
#endif

    return 0;
}
